package com.dateConstruction._04_BracketsMatch;

import _04_seqStack.SeqStack;
import _04_seqStack.Stack;

public class BracketsMatchBySeqStack {
    
    // 只适用于单个字符的括号
    public static String match(String target, String left, String right) {
        Stack<Integer> stack = new SeqStack<Integer>();
        for (int i = 0; i < target.length(); i++) {
            if (target.charAt(i) == left.charAt(0)) {
                stack.push(i);
            }
            if (target.charAt(i) == right.charAt(0)) {
                if (stack.isEmpty()) {
                    return "语法错误, target.charAt(" + i + "):'" + target.charAt(i) + "'多余";
                } else {
                    stack.pop();
                }
            }
        }
        if (!stack.isEmpty()) {
            return "语法错误, target.charAt(" + stack.peek() + "):'" + target.charAt(stack.peek()) + "'缺少'" + right + "'";
            
        } else {
            return "匹配";
        }
    }
    // 优化，适用于多个字符的括号，使用Brute-Force算法查找括号
    public static String match1(String target, String left, String right) {
        Stack<String> stack = new SeqStack<String>();
        int i = 0;
        while (i < target.length()) {
            while (i < target.length() && target.charAt(i) != left.charAt(0) && target.charAt(i) != right.charAt(0)) {
                i++;
            }
            //System.out.println(ss + ", " + i);
            if (target.indexOf(left, i) == i) {
                stack.push(left);
                i += left.length();
            } else if (target.startsWith(right, i)) {
                if (stack.isEmpty()) {
                    return "语法错误，i = " + i + "，多余" + right;
                }
                stack.pop();
                i += right.length();
            } else {
                i++;
            }
            
        }
        return (stack.isEmpty()) ? "匹配" : "语法错误，缺少" + right;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(match("13(5(fds()a13fd5", "(", ")"));
        System.out.println(match("13(5)fds))a13fd5", "(", ")"));
        System.out.println(match1("13((1546)())65)((466", "((", "))"));
        System.out.println(match1("13((154))6)())65)((46))6", "((", "))"));
        System.out.println(match("((1+2)*3+4)", "(", ")"));
        System.out.println(match("123+10*(45-50+20/((35-25)*2+10)-11", "(", ")"));
        System.out.println(match("45+(10-15)*(25+35)/(60-40))-11", "(", ")"));
    }
}